// 题目链接：https://www.acwing.com/problem/content/2/

// 1.DFS暴力搜素
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int v[N]; // 存储物品的体积
int w[N]; // 存储物品的价值
int n, m;

// x 表示在判断是否选择第x个物品装入背包
// spV 表示背包的剩余容量
int DFS(int x, int spV)
{
    if (x > n)
        return 0; // 全部物品都已经选完了，直接返回

    if (spV < v[x])
    { // 如果当前物品的体积大于背包的剩余容量，则跳过当前物品，选择下一个物品
        return DFS(x + 1, spV);
    }
    else
    { // 如果当前物品的体积小于等于背包的剩余容量，则取将此物品放入背包和不放入背包两种选择的最大值
        return max(DFS(x + 1, spV), DFS(x + 1, spV - v[x]) + w[x]);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    int res = DFS(1, m);
    printf("%d\n", res);

    return 0;
}

//-------------------------------------------------------------------------------------------
// 2. 记忆化搜索
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int v[N];      // 存储物品的体积
int w[N];      // 存储物品的价值
int mem[N][N]; // mem[i][j]表示从i ~ n这几个物品中选择物品放入背包，得到的最大总价值
int n, m;

// x 表示在判断是否选择第x个物品装入背包
// spV 表示背包的剩余容量
int DFS(int x, int spV)
{
    if (mem[x][spV])
        return mem[x][spV]; // 结果已经被记录下来了，直接返回

    int sum = 0;
    if (x > n)
    {
        sum = 0; // 全部物品都已经选完了，返回0
    }
    else if (spV < v[x])
    { // 如果当前物品的体积大于背包的剩余容量，则跳过当前物品，选择下一个物品
        sum = DFS(x + 1, spV);
    }
    else if (spV >= v[x])
    { // 如果当前物品的体积小于等于背包的剩余容量，则取将此物品放入背包和不放入背包两种选择的最大值
        sum = max(DFS(x + 1, spV), DFS(x + 1, spV - v[x]) + w[x]);
    }

    mem[x][spV] = sum;
    return sum;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    int res = DFS(1, m);
    printf("%d\n", res);

    return 0;
}

//------------------------------------------------------------------------------------
// 3. 动态规划，从下往上推
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int v[N];    // 存储物品的体积
int w[N];    // 存储物品的价值
int f[N][N]; // f[i][j]表示从i ~ n这几个物品中选择物品放入容量为j背包，得到的最大总价值
int n, m;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    // 从下往上推
    // 对于每个物品i，依次枚举背包容量为j的情况，得到每种情况的最大值
    for (int i = n; i >= 1; --i)
    {
        for (int j = 0; j <= m; ++j)
        {
            if (j < v[i])
            { // 背包不够装
                f[i][j] = f[i + 1][j];
            }
            else
            { // 背包装得下物品i，取装还是不装两种情况的最大值
                f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
            }
        }
    }
    // f[1][m]就是题目描述的情况，从第一个物品到第n个物品中选择，装入容量为m的背包中得到的最大总价值
    printf("%d\n", f[1][m]);

    return 0;
}

//------------------------------------------------------------------------------------
// 4. 动态规划，从上往下推
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int v[N];    // 存储物品的体积
int w[N];    // 存储物品的价值
int f[N][N]; // f[i][j]表示从i ~ n这几个物品中选择物品放入容量为j背包，得到的最大总价值
int n, m;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    // 从下往上推
    // 对于每个物品i，依次枚举背包容量为j的情况，得到每种情况的最大值
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            if (j < v[i])
            { // 背包不够装
                f[i][j] = f[i - 1][j];
            }
            else
            { // 背包装得下物品i，取装还是不装两种情况的最大值
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    // f[n][m]就是题目描述的情况，从第一个物品到第n个物品中选择，装入容量为m的背包中得到的最大总价值
    printf("%d\n", f[n][m]);

    return 0;
}

//------------------------------------------------------------------------------------
// 5. 动态规划，从下往上推 + 2个一维数组优化
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int v[N]; // 存储物品的体积
int w[N]; // 存储物品的价值
// 用两个一维数组，而不用一个二维数组，降低空间复杂度
int f[N]; // f[i]表示从k ~ n这几个物品中选择物品放入容量为i背包，得到的最大总价值
int g[N]; // g[i]表示从k ~ n这几个物品中选择物品放入容量为i背包，得到的最大总价值
int n, m;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    // 从下往上推
    // 对于每个物品i，依次枚举背包容量为j的情况，得到每种情况的最大值
    for (int i = n; i >= 1; --i)
    {
        for (int j = 0; j <= m; ++j)
        {
            if (j < v[i])
            { // 背包不够装
                g[j] = f[j];
            }
            else
            { // 背包装得下物品i，取装还是不装两种情况的最大值
                g[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
        memcpy(f, g, sizeof f);
    }
    // f[1][m]就是题目描述的情况，从第一个物品到第n个物品中选择，装入容量为m的背包中得到的最大总价值
    printf("%d\n", f[m]);

    return 0;
}

//------------------------------------------------------------------------------------
// 6. 动态规划，从下往上推 + 滚动数组
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;

int v[N]; // 存储物品的体积
int w[N]; // 存储物品的价值
int f[N]; // f[i]表示从k ~ n这几个物品中选择物品放入容量为i背包，得到的最大总价值
int n, m;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    // 从下往上推
    // 对于每个物品i，依次枚举背包容量为j的情况，得到每种情况的最大值
    for (int i = n; i >= 1; --i)
    {
        for (int j = m; j >= v[i]; --j)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    // f[m]就是题目描述的情况，从第一个物品到第n个物品中选择，装入容量为m的背包中得到的最大总价值
    printf("%d\n", f[m]);

    return 0;
}